#!/usr/bin/python
# -*- coding: UTF-8 -*-

"""
    题意：
        给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
        有效字符串需满足：
            左括号必须用相同类型的右括号闭合。
            左括号必须以正确的顺序闭合。

    示例：
        输入：s = "()"
        输出：true

        输入：s = "()[]{}"
        输出：true

        输入：s = "(]"
        输出：false

        输入：s = "([)]"
        输出：false

        输入：s = "{[]}"
        输出：true
"""

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """

        stack = []
        brackets = {
            ')': '(',
            '}': '{',
            ']': '[',
        }
        for i in s:
            if not stack or stack[-1] != brackets.get(i,''):
                stack.append(i)
            if stack and stack[-1] == brackets.get(i,''):
                stack.pop()
        print(stack)
        print(not stack)
        return not stack

# s = "()"
# s = "()[]{}"
# s = "(]"
# s = "([)]"
# s = "{[]}"
s = ")(){}"
# s= "(])"
Solution().isValid(s)